#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
using namespace std;
class Solution12
{
public:
    vector<vector<int>> vv;
    vector<int> tmp;
    vector<bool> check = { false,false,false,false,false,false,false };
    vector<vector<int>> permute(vector<int>& nums)
    {
        dfs(1, nums);
        return vv;
    }
    void dfs(int n, vector<int>& nums)
    {
        for (int i = 0;i < nums.size();i++)
        {
            if (check[i]) continue;
            tmp.push_back(nums[i]);
            check[i] = true;
            if (n == nums.size())
            {
                vv.push_back(tmp);
                tmp.pop_back();
                check[i] = false;
            }
            else
            {
                dfs(n+1, nums);
                tmp.pop_back();
                check[i] = false;
            }
        }
    }
};
class Solution56
{
public:
    vector<int> path;
    vector<vector<int>> vv;
    vector<vector<int>> subsets(vector<int>& nums)
    {
        dfs(nums, 0);
        return vv;
    }
    void dfs(vector<int>& nums, int i)
    {
        if (i == nums.size())
        {
            vv.push_back(path);
            return;
        }
        path.push_back(nums[i]);
        dfs(nums, i +1);
        path.pop_back();
        dfs(nums, i + 1);
    }
};
class Solution789
{
public:
    vector<int> path;
    int Sum = 0;
    int SumOfSubset(vector<int>& nums)
    {
        int sum = 0;
        for (auto e : nums) sum ^= e;
        return sum;
    }
    int subsetXORSum(vector<int>& nums)
    {
        dfs(nums, 0);
        return Sum;
    }
    void dfs(vector<int>& nums, int pos)
    {
        Sum += SumOfSubset(path);
        for (int i = pos;i < nums.size()-1;i++)
        {
            path.push_back(nums[i]);
            dfs(nums, pos + 1);
            path.pop_back();
        }
    }
};
class Solution88
{
public:
    vector<vector<int>> ret;
    vector<int> path;
    int target;
    vector<vector<int>> combinationSum(vector<int>& candidates, int _target)
    {
        target = _target;
        dfs(candidates, 0,0);
        return ret;
    }
    void dfs(vector<int>& nums, int sum, int pos)
    {
        if (sum >= target)
        {
            if (sum == target) ret.push_back(path);
            return;
        }
        for (int i = pos;i < nums.size();i++)
        {
            path.push_back(nums[i]);
            dfs(nums, sum + nums[i], i);
            path.pop_back();
        }
    }
};
class Solution
{
public:
    vector<bool> col, big1, big2;
    vector<vector<string>> ret;
    vector<string> method;
    int n;
    vector<vector<string>> solveNQueens(int _n)
    {
        n = _n;
        col.resize(n, false);
        big1.resize(2 * n, false);
        big2.resize(2 * n, false);
        dfs(0);
        return ret;
    }
    void dfs(int cur_row)
    {
        if (cur_row == n)
        {
            ret.push_back(method);
            return;
        }
        for (int i = 0;i < n;i++)
        {
            if (!col[i] && !big1[cur_row - i + n] && !big2[cur_row + i])
            {
                string tmp(n, '.');tmp[i] = 'Q';
                method.push_back(tmp);
                col[i] = true;big1[cur_row - i + n] = true;big2[cur_row + i] = true;
                dfs(cur_row + 1);
                method.pop_back();
                col[i] = false;big1[cur_row - i + n] = false;big2[cur_row + i] = false;
            }
        }
    }
};
int main()
{
	vector<int> nums = { 2,3,5 };
    vector<bool> check(8);
    string tmp(3, '.');
    Solution().solveNQueens(1);
	return 0;
}